
\section{Lower bound}
\label{sec:lowerbound} In this section, we show an almost tight
lower bound on the time complexity of performing a distributed
random walk.
%s, i.e., specifically for the {\em Single Random Walk} problem.
We show that any distributed algorithm needs  at least
$\Omega\left(\sqrt{\frac{\ell}{\log \ell}}\right)$ rounds, even in
graphs with low diameter. Note that $\Omega(D)$ is a  lower bound
\cite{DNP09-podc}. Also note that if a source node wants to sample
$k$ destinations from independent random walks, then $\Omega(k)$ is
also a lower bound as the source may need to receive $\Omega(k)$
distinct messages. Therefore, for $k$ walks, the lower bound we show
is $\Omega(\sqrt{\frac{\ell}{\log \ell}} + k + D)$ rounds. For small
diameter graphs, this almost matches our upper bound for $k=1$. (The
rest of the section omits the $\Omega(k+D)$ term.) In particular, we
show that there exists a $n$-node graph of diameter $O(\log n)$ such
that any distributed algorithm needs at least
$\Omega(\sqrt{\frac{n}{\log n}})$ time to perform a walk of length
$n$. Our lower bound proof makes use of a lower bound for another
problem that we call as the {\em path verification problem} defined
as follows:


\begin{definition}[{\sc Path-Verification} Problem]
The input of the problem consists of an integer $\ell$, a graph $G =
(V,E)$, and $\ell$ (not necessary distinct) vertices   $v_1, v_2,
..., v_\ell$ in $G$. The goal is for some node $v$  to  ``verify"
that the above sequence of vertices forms a $\ell$-length path (not
necessarily simple), i.e., if $(v_i,v_{i+1})$ forms an edge for $1
\leq i \leq \ell - 1$.  We assume that each  vertex knows  its order
number in the path (if the sequence indeed forms a path), i.e.,
$v_i$ knows the number $i$. Each vertex can (only) verify a segment
of the path that it knows either directly or indirectly, by learning
from its neighbors, as follows.
 Initially, every node $v_i$ has the interval $[i,i]$, i.e., it can verify its own position since it knows only its own order number.  In general, for any $i$ and $j$, if any node $u$ has (knows) all the index numbers from $i$ to $j$
then we say that the (sub-)path $v_i ,v_{i+1}, \dots ,v_j$ has been
verified by $u$. Any algorithm for this problem proceeds in rounds.
In each round, any node $u$ is allowed the following operation: For
each edge $(u,w)$, $u$ can send an interval $[i, j]$ that it has
already verified to $w$. After this operation, $w$ has all the index
numbers from $[i,j]$ (and thus also can verify  the path $v_i
,v_{i+1}, \dots ,v_j$).
 The
goal of this problem is to have the path $v_1, v_2, \dots, v_\ell$
verified by some node $v$. In other words, $v$ should verify  all
numbers from $1$ to $\ell$, using the smallest number of rounds
possible. \qed
\end{definition}


%{\bf Danupon:} 1) We don't need to specify $v$. We just want any node to verify the whole path at the end. (These two versions are
%equivalent though, as our graph has low diameter.) 2) When you talk about an edge $(u, v)$, is this $v$ the same as an input $v$? 3) Should
%we call the problem Walk Verification instead because sometimes people are confused between path and simple path.

%*************************************
%\begin{figure}
%\centering
%\includegraphics{path_verify_definition.eps}
%\caption{Example of path verification problem. {\bf (a)} In the beginning, we want to verify that the vertices containing numbers
%$1..5$ form a path. (In this case, they form a path $a, b, c, d, a$.) {\bf (b)} One way to do this is for $a$ to send $1$ to $b$
%and therefore $b$ can check that two vertices $a$ and $b$ corresponds to label $1$ and $2$ form a path. (The interval $[1,2]$
%is used to represent the fact that vertices corresponding to numbers $1, 2$ are verified to form a path.) Similarly, $c$ can verify
%$[3,5]$. {\bf (c)} Finally, $c$ combine $[1,2]$ with $[3, 5]$ and thus the path corresponds to numbers $1,2, ..., 5$ is verified.
%} \label{fig:path_verify_definition}
%\end{figure}
%**************************************

Thus the goal of the path verification problem is for some node $v$
to obtain a ``certificate" that verifies that the given sequence of
vertices is  a valid path of  length $\ell$. Each vertex can (only)
verify a segment of the path that it knows either directly or
indirectly (by learning form its neighbors as follows).\danupon{This
repeats what is said in the definition.} Initially each vertex knows
only the trivial segment itself. If a vertex obtains from its
neighbor a segment $[i_1,j_1]$ and if it has already verified
segment $[i2,j2]$ and if they overlap (say, $i_1 < i_2 < j_1 < j_2$)
then it can verify a larger interval ($[i_1,j_2]$).  Note that a
node needs to only send the endpoints of the interval that it can
verify (hence larger intervals are better). (See
Figure~\ref{fig:path_verify_definition} in the Appendix for an
example.) We would like to determine a lower bound for the running
time of any distributed algorithm for the above problem.

A lower bound for the path verification problem implies a lower
bound for the random walk problem. The reason is as follows. Both
problems involve constructing  a path of some specified length
$\ell$. Intuitively, the former is a simpler problem, since we  are
not verifying  whether the local steps are chosen randomly, but just
whether the path is valid and is of length $\ell$. On the other
hand, any algorithm for the random walk problem (including our
algorithm of Section \ref{sec:one_walk_DoS}), also solves the path
verification problem, since the path it constructs should be a valid
path of length $\ell$. It is straightforward to make any distributed
algorithm that computes a random walk  to also output a certificate
that it indeed is a valid walk of appropriate length.  This is
essential for correctness, as otherwise, an adversary can always
change  simply one edge of the graph and ensure that the walk is
wrong.

In the next section we first prove a lower bound for the path
verification problem. We then show that this implies the same lower
bound for the random walk problem, by giving reduction to a random
walk problem.

\subsection{Lower Bound for the Path Verification Problem}

The main result of this section is the following theorem.
\begin{theorem}
\label{thm:mainLB} For every $n$, and $\ell \leq n$ there exists a
graph $G_n$ of $\Theta(n)$ vertices and diameter $O(\log n)$, and a
path $P$ of length $\ell$ such that any algorithm  that solves the
{\sc Path-Verification} problem on $G_n$ and $P$ requires more than
$k$ rounds, where $k=\sqrt{\frac{\ell}{\log \ell}}$.
\end{theorem}


The rest of the section is devoted to proving the above Theorem. We
start by defining $G_n$.

\begin{definition}[Graph $G_{n}$] Let $k'$ be an integer such that
$k$ is a power of $2$ and $k'/2\leq 4k < k'$. Let $n'$ be such that
$n'\geq n$ and $k'$ divides $n'$. We construct $G_n$ having
$(n'+2k'-1)=O(n)$ nodes as follows. First, we construct a path
$P=v_1v_2...v_{n'}$. Second, we construct a binary $T$ having $k'$
leaf nodes. Let $u_1, u_2, ..., u_{k'}$ be its leaves from left to
right. Finally, we connect $P$ with $T$ by adding an edge
$u_iv_{jk'+i}$ for every $i$ and $j$. We will denote the root of $T$
by $x$ and its left and right children by $l$ and $r$ respectively.
Clearly, $G_n$ has diameter $O(\log n)$. We then consider a path of
length $\ell=\Theta(n)$. If we require $n$ to be much larger than
$\ell$, this is achieved by just adding dummy vertices to the graph
connected to the root of $T$. (The resulting graph $G_n$ is as in
Figure~\ref{fig:graph_construction} in the Appendix.) \qed
\end{definition}


%{\bf Gopal;} It wil be good to make the figures more clearer, larger if possible. We
%can try to put figures side by side to gain space.
%Explanations in Figure 4 and 5 have to be fixed for style.
%{\bf Danupon:} The figure could be larger by changing the width below (in the includegraphics ...).
%I've changed the picture a bit. I don't know what else to do to make it clearer.

%**********************************************************
%\begin{figure}
%  \centering
%  \includegraphics[width=0.7\linewidth]{Graph_Construction.eps}\\
%  \caption{$G_n$}\label{fig:graph_construction}
%\end{figure}
%**********************************************************


To prove the theorem, let $\mathcal A$ be any algorithm for the {\sc
Path-Verification} problem that solves the problem on $G_n$ in at
most $k'$ rounds. We need some definitions and claims to prove the
 theorem.


%(GOPAL --- It will be good to put all proofs of the lower bound in
%the main paper. It won't increase the space by too much and it will
%read much better.)



\noindent{\bf Definitions of {\em left/right subtrees} and {\em
breakpoints}.}

%{\bf Gopal:} In he definition of subtrees below, we have to make it clear that the subtree includes
%the nodes in the path also. Note that the graph is not tree if it includes the path, as there are cycles.
%We have to just clarify this.

%{\bf Danupon:} I added one more sentence. Hope it is clear now.

%Let the root $x$'s two neighbors be $r$ and $l$ (for right and left
%children respectively).

Consider a tree $T'$ obtained by deleting all edges in $P$. Notice
that nodes $v_{jk'+i}$, for all $j$ and $i \leq k'/2$ are in the
subtree of $T'$ rooted at $l$ and all remaining points are in the
subtree rooted at $r$. For any node $v$, let $sub(v)$ denote the
subtree rooted at node $v$. (Note that $sub(v)$ also include nodes
in the path $P$.) We denote the set of nodes that are leaves of
$sub(l)$ by $L$ (i.e., $L=sub(l)\cap P$) and the set of nodes that
are leaves in $sub(r)$ by $R$.

%{\bf Gopal:} I think it should be $k'$ in the first line below instead of $k$.
%Also carefully check the notations below, in particular, should it be " $v_{jk'+k+1}$"
%in the last line of the para below.

{%\bf Danupon:} $k$ in the first line is correct. I changed the sentence a bit. Hope it is clearer.
%Yes, it should be ``$v_{jk'+k+1}$" in the last line.


Since we consider an algorithm that takes at most $k$ rounds,
consider the situation when the algorithm is given $k$ rounds for
{\em free} to communicate only along the edges of the path $P$ at
the beginning.
%
Since $L$ and $R$ consists of every $k'/2$ vertices in $P$ and
$k'/2> 2k$, there are some nodes unreachable from $L$ by walking on
$P$ for $k$ steps. In particular, all nodes of the form
$v_{jk'+k'/2+k+1}$, for all $j$, are not reachable from $L$. We call
such nodes {\em breakpoints} for $sub(l)$. Similarly all nodes of
the form $v_{jk'+k+1}$, for all $j$, are not reachable from $R$ and
we call them the breakpoints for $sub(r)$. (See
Figure~\ref{fig:breaking-points} in the Appendix.)


%Let any
%node in $P$ that is not reachable from $L$ (i.e., $v_{jk'+k'/2+i}$,
%for all $j$ and $k < i < k'/2-k$) in the initial $k$ rounds be
%called a {\em breakpoint} for $sub(l)$. Similarly, any node that is
%not reachable from vertices in $R$ be called a {\em breakpoint} for
%$sub(r)$. In particular, all nodes of the form $v_{jk'+k'/2+k+1}$,
%for all $j$, are breakpoints for $sub(l)$. Let $B_l$ be the set of
%such nodes. Similarly all nodes of the form $v_{jk'+k+1}$, for all
%$j$ are breakpoints for $sub(r)$ and we let $B_r$ be the set of
%such nodes. (See Figure~\ref{fig:breaking-points}.)

%***********************************************************
%\begin{figure}
%\centering
%\includegraphics{breaking-points.eps}
%\caption{\textbf{Breakpoints.} {\bf (a)} $L$ and $R$ consist of every other $k'/2$ vertices in $P$.
%(Note that we show the vertices $l$ and $r$ appear many times for the convenience of presentation.)
%{\bf (b)} $v_{k'/2+k+1}$ and $v_{k'+k'/2+k+1}$ (nodes in black) are two of the breakpoints for $L$.
%Notice that there is one breakpoint in every connected piece of $L$ and $R$.} \label{fig:breaking-points}
%\end{figure}
%***********************************************************

\noindent{\bf Definitions of {\em path-distance} and {\em
covering}.}


%{\bf Gopal:} Again, does the "number of leaves below" include the nodes on the path below"

%{\bf Danupon:} I added one more sentence and changed the picture to clarify this.

For any two nodes $u$ and $v$ in $T'$ (obtained from $G_n$ by
deleting edges in $P$), let $c(u, v)$ be a lowest common ancestor of
$u$ and $v$. We define $path\_dist(u, v)$ to be the number of leaves
of subtree of $T$ rooted at $c(u, v)$. Note that the path-distance
is defined between any pair of nodes in $G_n$ but the distance is
counted using the number of leaves in $T$ (which excludes nodes in
$P$).
%(Recall that $T$ does not contain vertices in $P$.)
(See Figure~\ref{fig:path_distance} in the Appendix.)

%{\bf Gopal:} It is still confusing. When you say two nodes, they can also be nodes belonging to the path right?
%But then you are saying that $T$ does not include $P$.

%*********************************************************
%\begin{figure}
%\centering
%\subfigure[{Path-distance.}]{
%\includegraphics[width=0.35\linewidth]{path-distance.eps}
%\label{fig:path_distance}}
%%
%\subfigure[{Idea of Claim~\ref{claim:one}}]{
%\includegraphics[width=0.35\linewidth]{scratch_4.eps}
%\label{fig:scratch_4}
%}
%%
%\subfigure[Idea of Lemma~\ref{lem:three}.]{
%\includegraphics[width=0.25\linewidth]{max_path_cover.eps}
%\label{fig:max_path_cover}
%}
%\caption{{\bf (a)} Path distance between 1 and 2 is the
%number of leaves in the subtree rooted at 3,
%the lowest common ancestor of 1 and 2. {\bf (b)} For one unscratched left breakpoint, $k'/2+k+1$
%to be combined with another right breakpoint
%$k+1$ on the left, $k'/2+k+1$ has to be carried
%to $L$ by some intervals.
%Moreover, one interval can carry at most two
%unscratched breakpoints at a time. {\bf (c)} Sending a message between nodes on level $i$ and $i-1$ can
%increase the covered path distance by at most $2^i$}
%\end{figure}
%**********************************************************

%\begin{figure}
%\center
%\includegraphics[width=0.3\linewidth]{path-distance.eps}
%\caption{{\bf Path-distance.} Path distance between 1 and 2 is the
%number of leaves in the subtree rooted at 3,
%the lowest common ancestor of 1 and 2.} \label{fig:path_distance}
%\end{figure}

%Let us define the {\em path-distance} between two nodes $v_i$ and
%$v_j$ in $P$ as the distance between $v_i$ and $v_j$ on the path
%$v_1, v_2, \ldots, v_n$. That is $path\_dist(v_i, v_j) = |i-j+1|$. We
%also define the path distance between any two nodes in the graph in
%a similar manner: $path\_dist(x,y)$ is computed as $2^j$ where $j$ is
%the level of the first common ancestor of $x$ and $y$.

We also introduce the notion of the path-distance {\em covered} by a
message. For any message $m$, the path-distance covered by $m$ is
the maximum path-distance taken over all nodes that have held the
message $m$. That is, if $m$ covers some nodes $v'_1, v'_2, ...,
v'_k$ then the path-distance covered by $m$ is the number of leaves
in the subtrees of $T$ rooted by $v'_1, v'_2, ..., v'_k$. Note that
some leaves may be in more than one subtrees and they will be
counted only once. Proof of the following lemma can be found in
Appendix~\ref{proof:lem:one}.
%
%For any message $m$, the path-distance covered by $m$ is
%the maximum path-distance taken over all pairs of nodes that have
%held the message $m$.

%{\bf Gopal:} The above is a bit confusing. Since nodes on a path also hold the message, we need
%the notion of path-distance between any two nodes. So I guess, we should define path distance in the tree
%T' (T + vertices of P - edges of P). I think this is what you mean. See my previous comment.
%{\bf Danupon:} I also asked the same question earlier. I've redefine it as above.
%\textbf{Danupon:} What does this mean?

\begin{lemma}
\label{lem:one} The number of breakpoints for the left subtree and
for the right subtree are at least $\frac{n}{4k}$ each.
\end{lemma}




The reason we define these breakpoints is to show that the entire
information held by the left subtree has many disjoint intervals,
and same for the right subtree. This then tells us that the left
subtree and the right subtree must {\em communicate} a lot to be
able to merge these intervals by connecting/communicating the break
points. Proof of the following lemma is in
Appendix~\ref{proof:lem:two}.

%{\bf Gopal:} The term $path\_dist$ looks a bit ugly. I would put underscore or omit hyphen altogether.

%{\bf Danupon:} It is now path\_dist

\begin{lemma}
\label{lem:two} For algorithm $\mathcal A$ to solve {\sc
Path-Verification} problem, the total path-distance covered by all
messages is at least $n$.
\end{lemma}


%REMOVE AND USE SUBFIG INSTEAD
%\begin{figure}
%\center
%\includegraphics[width=0.3\linewidth]{scratch_4.eps}
%\caption{{\bf Idea of Claim~\ref{claim:one}} For one unscratched left breakpoint, $k'/2+k+1$
%to be combined with another right breakpoint
%$k+1$ on the left, $k'/2+k+1$ has to be carried
%to $L$ by some intervals.
%Moreover, one interval can carry at most two
%unscratched breakpoints at a time.} \label{fig:scratch_4}
%\end{figure}

These intervals can however be communicated using the tree edges as
well. We bound the maximum communication that can be achieved across
$sub(l)$ and $sub(r)$ indirectly by bounding the maximum
path-distance that can be covered in each round. In particular, we
show the following lemma (proved in Appendix~\ref{proof:lem:three}).

\begin{lemma}
\label{lem:three} In $k$ rounds, all messages together can cover at
most a path-distance of $O(k^2\log k)$.
\end{lemma}


%MOVED TO SUBFIGURE
%\begin{figure}
%\center
%\includegraphics{max_path_cover.eps}
%\caption{\textbf{Idea of Lemma~\ref{lem:three}.} Sending a message between nodes on level $i$ and $i-1$ can
%increase the covered path distance by at most $2^i$} \label{fig:max_path_cover}
%\end{figure}

We now describe the proof of the main theorem using these three
claims.

\begin{proof} [Proof of Theorem~\ref{thm:mainLB}]
Use Lemmas~\ref{lem:two} and~\ref{lem:three} we know that if
$\mathcal A$ solves {\sc Path-Verification}, then it needs to cover
a $path\_dist$ of $n$, but in $k$ rounds it can only cover a
$path\_dist$ of $O(k^2\log k)$. But this is $o(n)$ since
$k=\sqrt{\frac{n}{\log n}}$, contradiction.
\end{proof}

\iffalse We remark that the path verification problem can be solved
in $O(\sqrt{\ell} + D)$ rounds. The node that needs to verify the
path from $1$ to $n$ can ask node with id $i\sqrt{\ell}+1$ to verify
the path from $i\sqrt{\ell}$ to $(i+1)\sqrt{\ell}$, for all $0\leq
i\leq \sqrt{\ell}-1$. Each such piece can be verified in parallel,
in $O(\sqrt{\ell})$ rounds; this crucially uses the fact that the
path being verified is a simple path (i.e. no vertex/edge
repetitions) and the fact that it is numbered $1$ through $n$. In
case of random walks, there can be vertex repetitions; additionally,
the subsequent node ids of the walk steps are unknown. This is what
makes an upper bound for the random walk problem more involved. \fi

\subsection{Reduction to Random Walk Problem} \label{sec:reduction}
We now discuss how the lower bound for the path verification problem
implies the lower bound of the random walk problem. The main
difference between {\sc Path-Verification} problem and the random
walk problem is that in the former we can specify which path to
verify while the latter problem generates different path each time.
We show that the ``bad'' instance ($G_n$ and $P$) in the previous
section can be modified so that with high probability, the generated
random walk is ``hard'' to verify.




%{\bf Gopal}: Here we should discuss how the lower bound for the path verification
%implies a lower bound for a the random walk problem.  Just a short description how we can make a
%random walk can be made to walk the path of length $n$ in the above constructed graph (adding enough multiple
%edges to mimic weights). We can also point out that the same lower bound result will hold if the verification
%is done by starting point of the random walk (rather than the root).

%{\bf Danupon}: Is below enough? BTW, the path verification problem shouldn't specify that
%the path has to be verified by the root.


\begin{theorem}
For any $n$, there exists a graph $G_n$ of $\Theta(n)$ vertices and
diameter $O(\log n)$, and $\ell=\Theta(n)$ such that, with high
probability, a random walk of length $\ell$  needs
$\Omega(\sqrt{\frac{\ell}{\log \ell}})$  rounds.
\end{theorem}

\begin{proof}
First, note that Theorem~\ref{thm:mainLB} can be generalized to the
case where the path $P$ has infinite capacity, as follows.

\begin{theorem}
\label{thm:general-LB} For any $n$, there exists a graph $G_n$ of
$O(n)$ vertices and diameter $O(\log n)$, and a path $P$ of length
$\Theta(n)$ such that any algorithm that solves the {\sc
Path-Verification} problem on $G_n$ and $P$ requires more than $k$
rounds, even if edges in $P$ have large capacity (i.e., one can send
larger sized messages in one step), where $k=\sqrt{\frac{n}{\log
n}}$.
\end{theorem}

\begin{proof}
This is because the proof of Theorem~\ref{thm:mainLB} only uses the
congestion of edges in the tree $T$ (imposed above $P$) to argue
about the number of rounds.
\end{proof}

Now, we modify $G_n$ to $G'_n$ as follows. Recall that the path $P$
in $G_n$ has vertices $v_1, v_2, ..., v_{n'}$. For each $i=1, 2,
..., n'$, we define the weight of an edge $(v_i,v_{i+1})$ to be
$(2n)^{2i}$ (note that weighted graphs are equivalent to unweighted
multigraphs in our model). By having more weight, these edges have
more capacity as well. However, increasing capacity does not affect
the claim as shown above. Observe that, when the walk is at the node
$v_i$, the probability of walk will take the edge $(v_i,v_{i+1})$ is
at least $1-\frac{1}{n^2}$. Therefore, $P$ is the resulting random
walk with probability at least $1-1/n$. When the random walk path is
$P$, it takes at least $\sqrt{\frac{n}{\log n}}$ rounds to verify,
by Theorem~\ref{thm:general-LB}. This completes the proof.
%
%\textbf{Danupon:} The problem with the above proof is that the weights are really huge. So, we cannot call them multiple edge.
%One idea to fix this is to put only $2^i$ edges between $v_i$ and $v_{i+1}$ and argue that the walk will have length $\Omega(n)$ with
%high probability. Then, we need to modify the theorem to deal with paths of length, say $n/2$, as well. Is $2^n$ small enough?
%
%{\bf Gopal:} Why we cannot call them multiple edge (as I say in the proof above)? What is the differnece
%if the wieght is $2^i$ as opposed to $n^i$ ?
%{\bf Danupon:} My only worry is that $n^i$ is too much for the number of edges. (That's also true for $2^i$.)
%If you think it is fine then that is ok.
%
%Another idea is to only show that with constant probability that the path will be taken.
%Then our lower bound statement will hold with constant probability instead of high probablity.
%In this case, we need only polynomial weights -- $n^2$ will suffice for every edge in the path. Do you agree?
%If this is correct, we can state this also.
\end{proof}

%\subsection{Reduction to Random Walk Problem}
%\label{sec:reduction}
%
%%{\bf Gopal}: Here we should discuss how the lower bound for the path verification
%%implies a lower bound for a the random walk problem.  Just a short description how we can make a
%%random walk can be made to walk the path of length $n$ in the above constructed graph (adding enough multiple
%%edges to mimic weights). We can also point out that the same lower bound result will hold if the verification
%%is done by starting point of the random walk (rather than the root).
%
%%{\bf Danupon}: Is below enough? BTW, the path verification problem shouldn't specify that
%%the path has to be verified by the root.
%
%We now discuss how the result above implies the lower bound of the random walk problem.
%The main difference between {\sc Path-Verification} problem and the random walk problem is that in
%the former we can specify which path to verify while the latter problem generates different path each time.
%In this section we show that the ``bad'' instance ($G_n$ and $P$) in the previous section can be modified so that
%with high probability, the generated  random walk is ``hard'' to verify.
%
%\begin{theorem}
%For any $n$, there exists a graph $G_n$ of $O(n)$
%vertices and diameter $O(\log n)$, and $\ell=\Theta(n)$
%such that, with high probability, a random walk of length $\ell$ starting at $s$ needs
%$\sqrt{\frac{n}{\log n}}$ rounds to verify.
%\end{theorem}
%\begin{proof}
%First, note that Theorem~\ref{thm:mainLB} can be generalized to the case where the path $P$ has infinite
%capacity, as follows.
%
%\begin{theorem}
%\label{thm:general-LB} For any $n$, there exists a graph $G_n$ of $O(n)$
%vertices and diameter $O(\log n)$, and a path $P$ of length $\Theta(n)$
%such that any algorithm that
%solves the {\sc Path-Verification} problem on $G_n$ and $P$ requires more
%than $k$ rounds, even if edges in $P$ have large capacity (i.e., one can send larger sized messages in one step), where $k=\sqrt{\frac{n}{\log n}}$.
%\end{theorem}
%
%\begin{proof}
%This is because the proof of Theorem~\ref{thm:mainLB} only uses the congestion of edges in the tree $T$ (imposed above $P$)
%to argue about the number of rounds.
%\end{proof}
%
%Now, we modify $G_n$ to $G'_n$ as follows. Recall that the path $P$ in $G_n$ has vertices $v_1, v_2, ..., v_{n'}$.
%For each $i=1, 2, ..., n'$, we define the weight of an edge $(v_i,v_{i+1})$ to be $(2n)^{2i}$ (note that weighted
%graphs are equivalent to unweighted multigraphs in our model).
%By having more weight, these edges have more capacity as well. However, increasing capacity does not affect the claim
%in Theorem~\ref{thm:general-LB}. Observe that, when the walk is at the node $v_i$,
%the probability of walk will take the edge $(v_i,v_{i+1})$ is at least $1-\frac{1}{n^2}$. Therefore, $P$ is the resulting random
%walk with probability at least $1-1/n$. When the random walk path is $P$, it takes at least $\sqrt{\frac{n}{\log n}}$ rounds
%to verify, by Theorem~\ref{thm:general-LB}. This completes the proof.
%
%%\textbf{Danupon:} The problem with the above proof is that the weights are really huge. So, we cannot call them multiple edge.
%%One idea to fix this is to put only $2^i$ edges between $v_i$ and $v_{i+1}$ and argue that the walk will have length $\Omega(n)$ with
%%high probability. Then, we need to modify the theorem to deal with paths of length, say $n/2$, as well. Is $2^n$ small enough?
%
%%{\bf Gopal:} Why we cannot call them multiple edge (as I say in the proof above)? What is the differnece
%%if the wieght is $2^i$ as opposed to $n^i$ ?
%%{\bf Danupon:} My only worry is that $n^i$ is too much for the number of edges. (That's also true for $2^i$.)
%I%f you think it is fine then that is ok.
%
%%Another idea is to only show that with constant probability that the path will be taken.
%%Then our lower bound statement will hold with constant probability instead of high probablity.
%%In this case, we need only polynomial weights -- $n^2$ will suffice for every edge in the path. Do you agree?
%%If this is correct, we can state this also.
%\end{proof}
